package sliding_window;

import java.util.*;

public class findAnagrams {
    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        List<Integer> ret = findAnagrams(s, p);
        System.out.println(ret);
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();

        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        int len = 0;
        for(int i = 0;i < p.length();i++) {
            hash1[p.charAt(i)-'a']++;
            len++;
        }
        int left = 0;
        int right = 0;
        int count = 0;
        while(right < s.length()){
            //进窗口
            hash2[s.charAt(right)-'a']++;
            if(hash2[s.charAt(right)-'a'] <= hash1[s.charAt(right)-'a']) {
                count++;
            }

            if(right-left+1 > len) {//出窗口
                if(hash2[s.charAt(left)-'a'] <= hash1[s.charAt(left)-'a']) {
                    count--;
                }
                hash2[s.charAt(left)-'a']--;
                left++;
            }

            if(count == len) {
                ret.add(left);
            }
            right++;

        }
        return ret;
    }
}
